'''
Created on Aug 19, 2009

@author: echeek
'''

import math

def listPrimesBasic(maxvalue):
    sieve=range(maxvalue);
    sieve[1]=0;
    curprime=2;
    endpoint=math.ceil(math.sqrt(maxvalue));
    while curprime<endpoint:
        curval=curprime*2;
        while curval < maxvalue:
            sieve[curval]=0;
            curval+=curprime;
        while curprime<endpoint:
            curprime+=1;
            if(sieve[curprime]!=0):
                break;
    print 'sieve generated';
    primes=[2];
    i=3;
    while i<maxvalue:
        if( sieve[i]!=0):
            primes.append(i);
        i+=2;
    return primes
    
def bitSieve(maxvalue):
    sieve=0;
    curprime=2;
    endp=math.ceil(math.sqrt(maxvalue));
    while curprime<endp:
        marker=1<<curprime*2;
        curval=curprime*2;
        while curval<maxvalue:
            sieve|=marker;
            marker<<=curprime;
            curval+=curprime;
        marker=1<<curprime;
        while True:
            curprime+=1;
            marker<<=1;
            if((sieve & marker)==0):
                print curprime
                break;
    return sieve;

def isPrimeInSieve(value, sieve):
    mark=1<<value;
    return mark & sieve==0;
        
    
#listPrimesBasic(10000);